D - We Like AGC
DPっていうのは数秒で分かる。添字をいっぱい持たないといけないのも分かる。でも、遷移が分からん。恐ろしく分からん。
解説記事もやっぱり多い！！！自分も書いていくよ（質は置いておいて）
考察
まず、「組み合わせの数を$ 10^9+7で割った余りを求めて下さい」辺りで、「DPだな」と予想がつく。こういうのはだいたいDPであることが多いです（本当に？）。
DP基本形dp[n] // n文字目まで考えた時の〇〇の値を作って、dp[n]からdp[n+1]に遷移する時、どれくらいの状態が必要かを考えてみる。すると、「AGC,ACG,GAC,A?GC,AG?Cが入るか？」みたいなので条件分岐したいので、右端のラスト数文字を持っておくと（「むむ、ここに"C"を足すと"AGC"になってしまう！ 」みたいなのが計算できる、と言う意味で）遷移がしやすくなるのかな〜？という気持ちになる。
遷移を考える時に
制限がある時の遷移を直接考えるのが難しい時は、まず「制限がない場合」を考えると考えやすくなります。
問：長さがNのAGCT文字列は何通りあるか。
dp[n][A or G or C or T] // 最後の文字が{A,G,C,T}である文字列の組み合わせの数
遷移は、dp[i+1]["A","G","C","T"] += dp[i]["A","G","C","T"] みたいな感じです。
https://gyazo.com/d1bc89ba76a557c186967dbf740a934c
ここから、切りたいやつをカットする、と言う感じです。例えば
文字列に"AC"を入れてはいけない
と言う制約の時は、
https://gyazo.com/38c06ffa705fdde0283fc380a24f8653
こんな風にこのAからACへの遷移を止めれば良いわけです。こんな風に、〇〇を含まない…という時は、普段通り遷移していって、もしもACが出てきたらその遷移は断ち切る！みたいな感じでやっていきましょう（？）。
code:submit.cpp
using namespace std;
typedef long long int ll;
ll MOD = 1000000007;
// AGCを含むかどうか、判定する
bool containAGC(string s) { return s.find("AGC") != string::npos; }
// 入れ替えた時にAGCが入っていないか、判定する
bool ok(string s) {
bool res = true;
res = !containAGC(s); // AGCがそのまま入ってるやつ予防
for (int i = 0; i < s.size() - 1; i++) {
swap(si, si + 1); // 一回スワップしてみる if (containAGC(s)) res = false;
}
return res;
}
// ====================================================================
int main() {
int n;
cin >> n;
vector<map<string, ll>> dp(n + 1);
string AGCT = "AGCT";
for (int i = 0; i < n; i++) {
for (auto x : AGCT) {
string next = s.first + x; // "CAGG" + 'C' みたいな
if (next.size() > 4) next.erase(next.begin()); // 4文字以下になるように調整
if (ok(next)) { // もしもずらしてもAGCが入らないなら、次につなげられる
}
}
}
}
// n文字目の部分の総和を計算する
ll ans = 0;
ans += x.second;
ans %= MOD;
}
cout << ans << endl;
}
学んだこと
条件を満たす〇〇の数を求めなさい…系の問題の解き方の一つとして今回のような「i+1へつないでいく（もし制約に引っかかったらつなげることができない）」みたいなのが使えることがある
DPの遷移が全く生えない時は制約を考えずに、例えば今回の場合だとAGCT文字列の数だけ数える遷移の仕方を考えて、そこから詳しく考えていく、という方法が有効かもしれない